/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date Feb 28, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayList;
import java.util.Arrays;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given a collection of numbers that might contain duplicates,
 *              return all possible unique permutations.
 * 
 *              For example, [1,1,2] have the following unique permutations:
 *              [1,1,2], [1,2,1], and [2,1,1].
 */
public class PermutationsII {

	// failed in large judge
	class Solution1 {
		public ArrayList<ArrayList<Integer>> res;
		public ArrayList<Integer> list;

		public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
			res = new ArrayList<ArrayList<Integer>>();
			list = new ArrayList<Integer>();
			perm(num, 0);
			return res;
		}

		private void perm(int[] num, int cur) {
			if (cur >= num.length) {
				for (int i = 0; i < num.length; i++)
					list.add(num[i]);
				if (!res.contains(list))
					res.add(list);
				list = new ArrayList<Integer>();
			}

			for (int i = cur; i < num.length; i++) {
				if (i == cur) {
					perm(num, cur + 1);
				} else {
					swap(num, i, cur);
					perm(num, cur + 1);
					swap(num, i, cur);
				}
			}
		}

		private void swap(int[] num, int i, int j) {
			int temp = num[i];
			num[i] = num[j];
			num[j] = temp;
		}
	}

	// better solution
	class Solution2 {
		public ArrayList<ArrayList<Integer>> res;
		public ArrayList<Integer> list;
		public int[] temp;
		public ArrayList<Integer> value;
		public ArrayList<Integer> counter;

		public ArrayList<ArrayList<Integer>> permuteUnique(int[] num) {
			res = new ArrayList<ArrayList<Integer>>();
			list = new ArrayList<Integer>();
			value = new ArrayList<Integer>();
			counter = new ArrayList<Integer>();
			Arrays.sort(num);
			int val = num[0];
			int count = 1;
			for (int i = 1; i < num.length; i++) {
				if (val == num[i])
					count++;
				else {
					value.add(val);
					counter.add(count);
					val = num[i];
					count = 1;
				}
			}
			value.add(val);
			counter.add(count);
			temp = new int[num.length];
			perm(temp, 0);
			return res;
		}

		public void perm(int[] temp, int cur) {
			if (cur == temp.length) {
				for (int i = 0; i < temp.length; i++)
					list.add(temp[i]);
				res.add(list);
				list = new ArrayList<Integer>();
			} else {
				for (int i = 0; i < value.size(); i++) {
					if (counter.get(i) > 0) {
						counter.set(i, counter.get(i) - 1);
						temp[cur] = value.get(i);
						perm(temp, cur + 1);
						counter.set(i, counter.get(i) + 1);
					}
				}
			}
		}
	}

	@Test
	public void test() {
		System.out.println(new Solution1().permuteUnique(new int[]{1, 1, 2}));
		System.out.println(new Solution2().permuteUnique(new int[]{1, 1, 2}));
	}
}
